//最大前后缀
class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> Premax(n); //最大前缀
        Premax[0]=height[0];
        for(int i=1; i<n; i++)
            Premax[i]=max(Premax[i-1], height[i]);
        
        vector<int> SuffixMax(n); //最大后缀
        SuffixMax[n-1]=height[n-1];
        for(int i=n-2; i>=0; i--)
            SuffixMax[i]=max(SuffixMax[i+1], height[i]);
        
        int ans=0;
        for(int i=0; i<n; i++)
            ans+=min(Premax[i], SuffixMax[i])-height[i];
        return ans;
    }
};